#93. 复原 IP 地址

/**
 * 将纯数字字符串切分成所有可能的合法 IPv4 地址。
 *
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    // 保存所有已经完成的合法 IP 地址。
    const result = [];

    /**
     * 从 s[start] 开始选择下一个字段。
     *
     * @param {number} start 尚未处理的第一个字符下标
     * @param {string[]} path 已经选择并验证合法的字段
     */
    const dfs = (start, path) => {
        /*
         * IPv4 必须恰好包含 4 个字段。
         *
         * 到达 4 段后不能继续选择：
         * - 如果 start === s.length，说明 4 段刚好用完全部字符，可以记录答案；
         * - 如果 start < s.length，说明还有字符剩余，这条分支不是完整 IP。
         */
        if (path.length === 4) {
            if (start === s.length) {
                result.push(path.join('.'));
            }
            return;
        }

        /*
         * 枚举下一个字段的长度。IPv4 的每个字段只能有 1～3 位，
         * 所以当前递归节点最多产生 3 个子分支。
         */
        for (let len = 1; len <= 3; len++) {
            /*
             * [start, start + len) 超出字符串范围，说明剩余字符不够。
             * len 继续增大只会越界得更严重，因此直接结束循环。
             */
            if (start + len > s.length) break;

            // 截取当前候选字段，slice 的右边界 start + len 不包含在结果中。
            const seg = s.slice(start, start + len);

            /*
             * 当前字段不合法时直接 break，而不是 continue。
             *
             * 原因是从同一个 start 出发，后面的候选只会在 seg 右侧继续加数字：
             * - 如果 seg 因前导零非法，更长字段仍然有前导零；
             * - 如果 seg 已大于 255，更长字段只会更大。
             *
             * 因此当前起点后续的长度都无须再尝试。
             */
            if (!valid(seg)) break;

            /*
             * 当前字段合法，将读取位置向右移动 len 位，并递归选择下一段。
             *
             * [...path, seg] 会创建一个新数组，所以当前层的 path 不会被修改。
             * 递归返回后可以直接尝试下一个 len，不需要手动执行 path.pop()。
             */
            dfs(start + len, [...path, seg]);
        }
    };

    // 从字符串下标 0 开始，此时还没有选择任何字段。
    dfs(0, []);

    // DFS 结束后，result 中保存了所有合法切分方案。
    return result;
};

/**
 * 判断一个候选字符串能否作为 IPv4 的一个字段。
 *
 * 调用方已经保证 str 的长度在 1～3 之间，因此这里只需检查：
 * 1. 是否存在前导零；
 * 2. 数值是否不超过 255。
 *
 * @param {string} str
 * @return {boolean}
 */
function valid(str) {
    /*
     * 以 0 开头时，只有单独的 "0" 合法。
     * "00"、"01"、"010" 等都含有前导零。
     */
    if (str[0] === '0') return str.length === 1;

    // 一元加号把数字字符串转为 number，再检查 IPv4 字段的数值上界。
    return +str <= 255;
}

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    const result = [];

    /*
     * 所有递归层共享同一个 path。
     * 它位于函数内部，因此每次调用 restoreIpAddresses 都会创建独立数组，
     * 不会受到上一次调用的影响。
     */
    const path = [];

    /**
     * 从 s[start] 开始选择下一个字段。
     *
     * path 不需要作为参数传入，因为 dfs 可以通过闭包直接访问它。
     *
     * @param {number} start 尚未处理的第一个字符下标
     */
    const dfs = (start) => {
        // 已经选择 4 段后，判断是否也恰好用完了全部字符。
        if (path.length === 4) {
            if (start === s.length) {
                /*
                 * join() 返回一个新字符串，不会把 path 数组本身存入 result，
                 * 所以后续的 path.pop() 不会修改已经保存的答案。
                 */
                result.push(path.join('.'));
            }
            return;
        }

        // 下一段的长度只能是 1、2 或 3。
        for (let len = 1; len <= 3; len++) {
            // 剩余字符不足时，后续更大的 len 也会越界。
            if (start + len > s.length) break;

            const segment = s.slice(start, start + len);

            /*
             * 当前字段非法后，更长字段也不会合法：
             * 前导零会一直保留，超过 255 的数字也只会继续增大。
             */
            if (!isValidSegment(segment)) break;

            // 1. 做选择：把当前字段加入路径。
            path.push(segment);

            // 2. 进入下一层：从当前字段之后继续切分。
            dfs(start + len);

            /*
             * 3. 撤销选择：恢复进入当前分支前的 path。
             *
             * 所有分支共享同一个数组，如果缺少 pop()，当前字段会残留，
             * 进而污染 for 循环中的下一个分支。
             */
            path.pop();
        }
    };

    dfs(0);
    return result;
};

/**
 * 判断字段是否合法。
 *
 * @param {string} segment
 * @return {boolean}
 */
function isValidSegment(segment) {
    // 多位字段不能以 0 开头，但单独的 "0" 合法。
    if (segment.length > 1 && segment[0] === '0') {
        return false;
    }

    return Number(segment) <= 255;
}

path.push(segment); // 做选择
dfs(nextStart);     // 递归处理下一层
path.pop();         // 撤销选择

dfs(start + len, [...path, seg]);
// 等价于：
dfs(6 + 2, ["255", "255", "11"]);

result.push(path.join('.'));

[...path, seg]

path.push(seg);      // 做选择
dfs(start + len, path);
path.pop();          // 撤销选择，恢复父层状态

path.length === 4
start === s.length